package offer.linkedList;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-02-20 21:45
 */
public class n_6 {
    public static void main(String[] args) {
        n_6 n = new n_6();
        ListNode n1 = new ListNode(67);
        ListNode n2 = new ListNode(0);
        ListNode n3 = new ListNode(24);
        ListNode n4 = new ListNode(58);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        ArrayList<Integer> res = n.printListFromTailToHead4(n1);
        System.out.println(res);
    }

    /**
     * 我的写法-递归
     */
    ArrayList<Integer> list = new ArrayList<Integer>();

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) {
            return list;
        }
        printListFromTailToHead(listNode.next);
        list.add(listNode.val);
        return list;
    }

    /**
     * 大神的递归写法
     *
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        if (listNode != null) {
            list.addAll(printListFromTailToHead2(listNode.next));
            list.add(listNode.val);
        }
        return list;

    }

    /**
     * 大神-头插法
     *
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ListNode curNode = listNode;
        ListNode head = new ListNode(-1);
        while (curNode != null) {
            ListNode tmp = curNode.next;
            curNode.next = head.next;
            head.next = curNode;
            curNode = tmp;
        }
        ArrayList<Integer> list = new ArrayList<>();
        head = head.next;
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return list;
    }

    /**
     * 大神-使用栈
     *
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead4(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

}
